package com.bascker.algorithm.practice.search.bfs;

import com.bascker.algorithm.base.queue.Queue;
import com.bascker.algorithm.base.queue.impl.ListQueue;
import com.bascker.algorithm.base.tree.TreeNode;
import com.bascker.algorithm.common.util.TreeUtil;
import com.google.common.collect.Sets;

import java.util.Objects;
import java.util.Set;

/**
 * 二叉树的最小深度: 给定一个二叉树，找出其最小深度
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量
 * <p>
 * in:      3               out: 2
 * / \
 * 9  20
 * /  \
 * 15   7
 *
 * @apiNote leetcode T111
 */
public class MinDepth {

    /**
     * BFS 解法
     */
    public int minDepth(final TreeNode<Integer> root) {
        final Queue<TreeNode<Integer>> queue = new ListQueue<>();
        final Set<TreeNode<Integer>> visited = Sets.newHashSet();

        // 头结点入队
        queue.enqueue(root);
        visited.add(root);
        // 根节点树深为 1
        int depth = 1;

        while (queue.isNotEmpty()) {
            final int len = queue.size();
            // 将队列中的结点向四周扩散
            for (int i = 0; i < len; i++) {
                final TreeNode<Integer> node = queue.dequeue();

                // 若当前结点是叶子结点，则终止
                if (TreeUtil.isLeafNode(node)) {
                    return depth;
                }

                if (Objects.nonNull(root.getLeft()) && !visited.contains(root.getLeft())) {
                    queue.enqueue(root.getLeft());
                    visited.add(root.getLeft());
                }

                if (Objects.nonNull(root.getRight()) && !visited.contains(root.getRight())) {
                    queue.enqueue(root.getRight());
                    visited.add(root.getRight());
                }
            }

            depth++;
        }

        return depth;
    }


}
